import java.util.Arrays;

/**
 * 1640. 能否连接形成数组
 * https://leetcode-cn.com/problems/check-array-formation-through-concatenation/
 */
public class Solutions_1640 {
    public static void main(String[] args) {
//        int[] arr = {85};
//        int[][] pieces = {{85}};  // output: true

//        int[] arr = {15, 88};
//        int[][] pieces = {{88}, {15}};  // output: true

//        int[] arr = {49, 18, 16};
//        int[][] pieces = {{16, 18, 49}};  // output: false

//        int[] arr = {1, 2, 3};
//        int[][] pieces = {{2}, {1, 3}};  // output: false

//        int[] arr = {91, 4, 64, 78};
//        int[][] pieces = {{78}, {4, 64}, {91}};  // output: true

        int[] arr = {1, 3, 5, 7};
        int[][] pieces = {{2, 4, 6, 8}};  // output: false

        boolean result = canFormArray(arr, pieces);
        System.out.println(result);
    }

    public static boolean canFormArray(int[] arr, int[][] pieces) {
        // map[5] = 3，数字 5 在 arr 中的下标是 2
        // map[5] = 1，数字 5 在 arr 中的下标是 0
        // map[5] = 0，数字 5 在 arr 不存在
        int[] map = new int[101];
        Arrays.fill(map, - 1);
        for (int i = 0; i < arr.length; i++) {
            map[arr[i]] = i;
        }
        for (int[] piece : pieces) {
            // 取出第一个元素
            int start = map[piece[0]];
            if (start < 0) {
                // piece[0] 元素不存在
                return false;
            }
            int limit = start + piece.length;
            if (limit > arr.length) {
                // 超出 arr 数组的范围
                return false;
            }
            for (int i = 0; i < piece.length; i++) {
                if (map[piece[i]] < 0) {
                    // 未出现
                    return false;
                }
                if (piece[i] != arr[i + start]) {
                    // 顺序不一致
                    return false;
                }
            }
        }
        return true;
    }
}
